package algorithm.dongtaiguihua;

import org.junit.Test;

public class BianjiJuli2 {

  @Test
  public void test(){
    System.out.println(minDistance("horse",
            "ros"));
  }

  public int minDistance(String word1, String word2) {

    int min = 0;
    int [][] dp = new int[word1.length()+1][word2.length()+1];
    //初始化
    for(int j = 0;j<word2.length()+1;j++){
      dp[0][j] = j;
    }
    for(int i = 0;i<word1.length()+1;i++){
      dp[i][0] = i;
    }

    for(int i = 1;i<word1.length()+1;i++){
      char a = word1.charAt(i-1);
      for(int j = 1;j<word2.length()+1;j++){
        char b = word2.charAt(j-1);
        if( a!=b ){
          dp[i][j] = Math.min( Math.min(dp[i-1][j],dp[i][j-1])+1,dp[i-1][j-1]+1);
        }else{
          dp[i][j] =  dp[i-1][j-1];
        }
        System.out.println(  i + " " + j + " " + dp[i][j] );
      }
    }
    return dp[word1.length()][word2.length()];
  }

}
